/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * 时间和空间复杂度都是O(n)
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head === null || head.next === null) return false

    let headSet = new Set(),
        temp = head

    while (temp !== null) {
        if (headSet.has(temp)) {
            return true
        } else {
            headSet.add(temp)
        }
        temp = temp.next
    }
    
    return false  
};
/**
 * 快慢指针，空间复杂度是O(1)
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head === null || head.next === null) return false

    let slow = head,
        fast = head.next

    while (slow !== fast) {
        if (fast === null || fast.next === null) return false
        slow = slow.next
        fast = fast.next.next
    }

    return true
};


function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

let a = new ListNode(4)
a.next = new ListNode(1)
a.next.next = new ListNode(8)
a.next.next.next = new ListNode(4)
a.next.next.next.next = new ListNode(5)
a.next.next.next.next.next = a.next
